Tracy–Widom distribution is a universal rule describing the distribution of any set of correlated variables. Instead of the smooth bell curve found with Gaussian distribution for uncorrelated variables, this distribution gives an asymmetrical statistical bump for correlated variables. The left side is steeper than the right and its summit sits at a scalable, universal value of 2N. This is also referred to as the transition point or crossover function between between stability and instability in various systems.

Networks describe the, often complex, relationships between individual actors. In this work, we address the question of how to determine whether a parametric model, such as a stochastic block model or latent space model, fits a dataset well and will extrapolate to similar data. We use recent results in random matrix theory to derive a general goodness-of-fit test for dyadic data. We show that our method, when applied to a specific model of interest, provides an straightforward, computationally fast way of selecting parameters in a number of commonly used network models. For example, we show how to select the dimension of the latent space in latent space models. Unlike other network goodness-of-fit methods, our general approach does not require simulating from a candidate parametric model, which can be cumbersome with large graphs, and eliminates the need to choose a particular set of statistics on the graph for comparison. It also allows us to perform goodness-of-fit tests on partial network data, such as Aggregated Relational Data. We show with simulations that our method performs well in many situations of interest. We analyze several empirically relevant networks and show that our method leads to improved community detection algorithms. R code to implement our method is available on Github.

Latent Block Models are used for probabilistic biclustering, which is shown to be an effective method for analyzing various relational data sets. However, there has been no statistical test method for determining the row and column cluster numbers of Latent Block Models. Recent studies have constructed statistical-test-based methods for Stochastic Block Models, in which we assume that the observed matrix is a square symmetric matrix and that the cluster assignments are the same for rows and columns. In this paper, we develop a goodness-of-fit test for Latent Block Models, which tests whether an observed data matrix fits a given set of row and column cluster numbers, or it consists of more clusters in at least one direction of row and column. To construct the test method, we use a result from random matrix theory for a sample covariance matrix. We show experimentally the effectiveness of our proposed method, by showing the asymptotic behavior of the test statistic and the test accuracy.

We study the problem of detecting an abrupt change to the signal covariance matrix. In particular, the covariance changes from a "white" identity matrix to an unknown spiked or low-rank matrix. Two sequential change-point detection procedures are presented, based on the largest and the smallest eigenvalues of the sample covariance matrix. To control false-alarm-rate, we present an accurate theoretical approximation to the average-run-length (ARL) and expected detection delay (EDD) of the detection, leveraging the extreme eigenvalue distributions from random matrix theory and by capturing a non-negligible temporal correlation in the sequence of scan statistics due to the sliding window approach. Real data examples demonstrate the good performance of our method for detecting behavior change of a swarm.

Community detection in networks is a key exploratory tool with applications in a diverse set of areas, ranging from finding communities in social and biological networks to identifying link farms in the World Wide Web. The problem of finding communities or clusters in a network has received much attention from statistics, physics and computer science. However, most clustering algorithms assume knowledge of the number of clusters k. In this paper we propose to automatically determine k in a graph generated from a Stochastic Blockmodel. Our main contribution is twofold; first, we theoretically establish the limiting distribution of the principal eigenvalue of the suitably centered and scaled adjacency matrix, and use that distribution for our hypothesis test. Secondly, we use this test to design a recursive bipartitioning algorithm. Using quantifiable classification tasks on real world networks with ground truth, we show that our algorithm outperforms existing probabilistic models for learning overlapping clusters, and on unlabeled networks, we show that we uncover nested community structure.